package com.Questions.DFS;

import java.util.*;
/**
 * 组合总数3
 */
public class leetcode216 {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    /**
     * 返回所有相加之和为n的k个数的组合 只能使用数字1到9 每一个数字最多使用一次
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 对于每一个1到9数字 可以跳过 也可以选择
        // 在9 个数字中选择 k个数字 判断和是否为 n
        dfs(1,9,k,n);
        return ans;
    }

    private void dfs(int cur, int n, int k, int sum) {
        if(temp.size() + (n - cur + 1) < k || temp.size() > k){// 对于现在构成的数组temp 如果他的长度加上剩余 数字的长度不足以构成答案 或者他的长度已经超过答案长度 直接返回
            return;
        }
        if(temp.size() == k) {// 已经选择了 k 个数字作为答案
            int tempSum = 0;
            for (int num : temp) {
                tempSum += num;
            }
            if(tempSum == sum) {
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
        }
        temp.add(cur);
        dfs(cur + 1,n,k,sum);// 因为 每一个数字只能选择一次 所以 无论是否选择该数字 都要跳到下一个
        temp.remove(temp.size() - 1);
        dfs(cur + 1,n,k,sum);
    }
}
